package com.leetcode.sorts.linked;

/**
 * @Author: WuPeng
 * @Date: 2021/5/26 7:26 下午
 *
 * 面试题02.07：链表相交
 * 给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，
 * 而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同
 * 一节点（引用完全相同），则这两个链表相交。
 *
 *
 */
public class CrossLinked {

    public static ListNode isCross(ListNode headA, ListNode headB){
        ListNode tmp1 = headA;
        ListNode tmp2 = headB;

        int len_A = 0;
        int len_B = 0;

        while (tmp1 != null || tmp2 != null){
            if (tmp1 != null) {
                tmp1 = tmp1.next;
                len_A++;
            }
            if (tmp2 != null) {
                tmp2 = tmp2.next;
                len_B++;
            }
        }

        tmp1 = headA;
        tmp2 = headB;
        if (len_A < len_B){
            int tmp = len_A ^ len_B;
            len_A = tmp ^ len_A;
            len_B = tmp ^ len_B;

            tmp1 = headB;
            tmp2 = headA;
        }

        int gap = len_A-len_B;
        while (gap-- > 0){
            tmp1 = tmp1.next;
        }
        while (tmp1 != null){
            if (tmp1 == tmp2){
                return tmp1;
            }
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
        return null;
    }

    public static void main(String[] args) {
        ListNode headA = new ListNode(4);
        ListNode nodeA1 = new ListNode(1);

        ListNode headB = new ListNode(5);
        ListNode nodeB1 = new ListNode(0);
        ListNode nodeB2 = new ListNode(1);

        ListNode node2 = new ListNode(8);
        ListNode node3 = new ListNode(4);
        ListNode node4 = new ListNode(5);
        headA.next  = nodeA1;
        nodeA1.next = node2;

        headB.next  = nodeB1;
        nodeB1.next = nodeB2;
        nodeB2.next = node2;

        node2.next = node3;
        node3.next = node4;

        ListNode cross = isCross(headA, headB);
        if (cross != null){
            System.out.println(cross.val);
        } else {
            System.out.println("");
        }
    }

}
